package com.arrays;

public class FindFirstandLastPositionofElementinSortedArray0123_34 {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0 || target<nums[0] || target>nums[nums.length-1]) return new int[]{-1,-1};

        //找左边界
        int left = 0, right = nums.length-1;
        while (left <= right){
            int mid = (left + right) /2;
            if (nums[mid] >= target) right = mid-1;
            if (nums[mid] < target) left = mid+1;
        }
        int leftBorder = right;

        //找右边界
        left = leftBorder; right = nums.length-1;
        while (left <= right){
            int mid = (left + right) /2;
            if (nums[mid] <= target) left = mid+1;
            if (nums[mid] > target) right = mid-1;
        }
        int rightBorder = left;

        if(rightBorder - leftBorder < 2) return new int[]{-1,-1}; // 内部 不含目标值
        return new int[]{leftBorder+1,rightBorder-1};
    }
}
